The invention relates generally to the field of digital communications systems and more particularly to digital networks for facilitating communication of digital data in, for example, digital image, audio and video distribution systems and among digital computer systems
Digital networks have been developed to facilitate the transfer of information, including data and programs, among digital computer systems and other digital devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In some networks, such as the well-known Ethernet, a single wire is used to interconnect all of the devices connected to the network. While this simplifies wiring of the network in a facility and connection of the devices to the network, it results in generally slow information transfer, since the wire can only carry information, in the form of messages, from a single device at a time. To alleviate this to some extent, in some Ethernet installations, the network is divided into a number of sub networks, each having a separate wire, with interfaces interconnecting the wires. In such installations, wires can carry messages for devices connected thereto simultaneously, which increases the number of messages that can be transferred simultaneously. It is only when a device connected to one wire needs to send a message to a device connected to another wire that wires in two or more sub-networks will be used, making them unavailable for use by other devices connected thereto.
To alleviate this, networks have been developed in which communications are handled through a mesh of switching nodes. The computer systems and other devices are connected to various ones of the switching nodes. Since the switching nodes themselves are interconnected in a variety of patterns, a number of paths may be available between pairs of the devices, so that if one path is congested, another may be used. Such an arrangement may result in a network which is more complicated than an Ethernet network, but it can provide substantially higher information transfer rates, particularly if optical fiber is used as the media interconnecting the switching nodes and devices. A problem which may arise with such networks is that, in such networks, a switching node or a device, when it is receiving information from another switching node or device in the network, does not have a mechanism to provide xe2x80x9cflow-controlxe2x80x9d information to the transmitting switching node or device. While this does reduce the cost of a network, it may result in congestion, in which a switching node may receive information at a rate faster than it can transmit it.
This problem has been addressed in one type of network, namely, a network implemented in accordance with the ATM (xe2x80x9cAsynchronous Transfer Modexe2x80x9d) methodology. In such a network, a xe2x80x9cpacketxe2x80x9d of data is transmitted from a source device to one or more destination devices in a series of xe2x80x9ccells.xe2x80x9d If a switching node detects congestion, such that it is receiving cells faster than it can transmit them, it can make use of several mechanisms. In one such mechanism, identified as xe2x80x9cearly packet discard,xe2x80x9d which may be used if a moderate amount of congestion is experienced, the switching node first refuses to accept cells related to any new packets, but it attempts to continue transferring cells associated with packets it has already begin transferring. This may alleviate the congestion downstream of the switching node, or at least provide that it does not increase. However, the congestion may continue increasing to a point where the node activates a second mechanism, identified as xe2x80x9cpartial packet discard.xe2x80x9d In the partial packet discard mechanism, if the switching node, due to increased congestion, has to drop one cell for a packet that it has begun transferring, it will continue dropping the cells from the same packet because all of the cells for a packet are required to correctly reassemble the packet at the destination. If the partial packet discard mechanism is activated due to congestion, partial packet discard should reduce it, but the packets which have been discarded may be re-transmitted by the source, so the switching nodes""s resources used to transfer the cells prior to activation of the partial packet discard mechanism were wasted.
A problem arises, however, in connection with the cell or packet discard mechanisms used in ATM networks. In particular, the ATM transfer methodology defines a number of types of service classes, and, for several of those service classes, service rate and cell loss guarantees may be provided. For connections which have a particular service rate guarantee, each switching node handling cells for a particular user will guarantee that cells associated with those connections will be transferred at least at a particular minimum rate through the network. This service rate may differ as among the various network users. Users may be provided with a minimum service rate, in which case they expect to be provided with at least a specified minimum rate, but may be transferred at a faster rate when there is available transfer bandwidth above the bandwidth that required for the connections for which there is a service rate guarantee. In addition, if cell loss guarantees are provided, the switching nodes handling cells for a particular user will guarantee that they will only lose, discard or otherwise fail to transfer cells for the user at a particular cell loss rate. The problem arises in that care must be taken to identify users for which cells can be discarded, to ensure that their guarantees are observed.
The invention provides a new and improved system and method for controlling the cell loss in a digital network to ensure that the cell loss guarantees provided by the network are observed.
In brief summary, the invention provides a switching node for use in connection with a computer network. The switching node includes an input interface, a buffer and a control element. The input interface receives cells from at least one input communication link. The buffer buffers selected cells prior to transmission over at least one output communication link. The control element selectively enables cells received by said input interface to be buffered in said buffer. The control element discards cells if the cell occupancy of the buffer exceeds a predetermined threshold level and a credits value indicates that the switching node has loaded a number of cells into the buffer for transmission which exceeds a cell loss ratio guarantee provided by the switching node. In one embodiment, the switching node provides an individual cell loss ratio guarantee for each virtual circuit being handled by the switching node. In that embodiment, the control element determines a credits value associated with each virtala circuit, the credits value indicating whether the switching node has properly transmitted cells for the virtual circuit at a rate which exceeds the cell loss ratio guarantee. If the credits value indicates that the switching node has transmitted cells for the virtual circuit at such a rate, if the cell occupancy of the buffer exceeds the threshold, a cell associated with the virtual circuit can be discarded and the switching node will still meet its cell loss ratio guarantee. The control element can perform these operations in connection with each of the virtual circuits being handled by the switching node, thereby permitting a balancing of cell loss among the virtual circuits in accordance with their respective cell loss ratio guarantees, when the cell occupancy of the buffer exceeds the predetermined threshold level.